{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Score After Applying Operations on a Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumScoreAfterOperations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #在树上执行操作以后得到的最大分数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一棵 <code>n</code>&nbsp;个节点的无向树，节点编号为 <code>0</code>&nbsp;到 <code>n - 1</code>&nbsp;，根节点编号为 <code>0</code>&nbsp;。给你一个长度为 <code>n - 1</code>&nbsp;的二维整数数组&nbsp;<code>edges</code>&nbsp;表示这棵树，其中&nbsp;<code>edges[i] = [a<sub>i</sub>, b<sub>i</sub>]</code>&nbsp;表示树中节点&nbsp;<code>a<sub>i</sub></code>&nbsp;和&nbsp;<code>b<sub>i</sub></code>&nbsp;有一条边。</p>\n",
    "\n",
    "<p>同时给你一个长度为 <code>n</code>&nbsp;下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>values</code>&nbsp;，其中&nbsp;<code>values[i]</code>&nbsp;表示第 <code>i</code>&nbsp;个节点的值。</p>\n",
    "\n",
    "<p>一开始你的分数为 <code>0</code>&nbsp;，每次操作中，你将执行：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>选择节点&nbsp;<code>i</code>&nbsp;。</li>\n",
    "\t<li>将&nbsp;<code>values[i]</code>&nbsp;加入你的分数。</li>\n",
    "\t<li>将&nbsp;<code>values[i]</code>&nbsp;变为&nbsp;<code>0</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果从根节点出发，到任意叶子节点经过的路径上的节点值之和都不等于 0 ，那么我们称这棵树是 <strong>健康的</strong>&nbsp;。</p>\n",
    "\n",
    "<p>你可以对这棵树执行任意次操作，但要求执行完所有操作以后树是&nbsp;<strong>健康的</strong>&nbsp;，请你返回你可以获得的 <strong>最大分数</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/10/11/graph-13-1.png\" style=\"width: 515px; height: 443px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>edges = [[0,1],[0,2],[0,3],[2,4],[4,5]], values = [5,2,5,2,1,1]\n",
    "<b>输出：</b>11\n",
    "<b>解释：</b>我们可以选择节点 1 ，2 ，3 ，4 和 5 。根节点的值是非 0 的。所以从根出发到任意叶子节点路径上节点值之和都不为 0 。所以树是健康的。你的得分之和为 values[1] + values[2] + values[3] + values[4] + values[5] = 11 。\n",
    "11 是你对树执行任意次操作以后可以获得的最大得分之和。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/10/11/graph-14-2.png\" style=\"width: 522px; height: 245px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]], values = [20,10,9,7,4,3,5]\n",
    "<b>输出：</b>40\n",
    "<b>解释：</b>我们选择节点 0 ，2 ，3 和 4 。\n",
    "- 从 0 到 4 的节点值之和为 10 。\n",
    "- 从 0 到 3 的节点值之和为 10 。\n",
    "- 从 0 到 5 的节点值之和为 3 。\n",
    "- 从 0 到 6 的节点值之和为 5 。\n",
    "所以树是健康的。你的得分之和为 values[0] + values[2] + values[3] + values[4] = 40 。\n",
    "40 是你对树执行任意次操作以后可以获得的最大得分之和。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= n &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>edges.length == n - 1</code></li>\n",
    "\t<li><code>edges[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt; n</code></li>\n",
    "\t<li><code>values.length == n</code></li>\n",
    "\t<li><code>1 &lt;= values[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li>输入保证&nbsp;<code>edges</code>&nbsp;构成一棵合法的树。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-score-after-applying-operations-on-a-tree](https://leetcode.cn/problems/maximum-score-after-applying-operations-on-a-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-score-after-applying-operations-on-a-tree](https://leetcode.cn/problems/maximum-score-after-applying-operations-on-a-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,1],[0,2],[0,3],[2,4],[4,5]]\\n[5,2,5,2,1,1]', '[[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]\\n[20,10,9,7,4,3,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "            \n",
    "        \n",
    "        @cache\n",
    "        def dfs(node, par, one_left):\n",
    "\n",
    "            neis = [x for x in g[node] if x != par]\n",
    "            if not neis:\n",
    "                return values[node] if one_left else 0\n",
    "\n",
    "            return max(values[node] + sum(dfs(nei, node, one_left) for nei in neis), sum(dfs(nei, node, True) for nei in neis))\n",
    "\n",
    "\n",
    "        return dfs(0, -1, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        g = [[] for i in range(n)]\n",
    "        deg = [0] * n\n",
    "        for i, j in edges:\n",
    "            g[i].append(j)\n",
    "            g[j].append(i)\n",
    "            deg[i] += 1\n",
    "            deg[j] += 1\n",
    "        deg[0] += 1\n",
    "\n",
    "        ans = [float('inf')] * n\n",
    "        queue = deque()\n",
    "        for idx, i in enumerate(deg):\n",
    "            if i == 1:\n",
    "                queue.append(idx)\n",
    "                ans[idx] = values[idx]\n",
    "        \n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            for i in g[node]:\n",
    "                deg[i] -= 1\n",
    "                if deg[i] == 1:\n",
    "                    children = sum([ans[x] for x in g[i] if deg[x] <= 1])\n",
    "                    ans[i] = min(values[i], children)\n",
    "                    queue.append(i)\n",
    "\n",
    "        return sum(values) - ans[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        dct = [[] for _ in range(n)]\n",
    "        for i, j in edges:\n",
    "            dct[i].append(j)\n",
    "            dct[j].append(i)\n",
    "\n",
    "        dp1 = [0 for _ in range(n)]\n",
    "        dp2 = [0 for _ in range(n)]\n",
    "        stack = [(0, -1)]\n",
    "        while stack:\n",
    "            # bujiankang, jiankang\n",
    "            x, fa = stack.pop()\n",
    "            if x >= 0:\n",
    "                stack.append((~x, fa))\n",
    "                for y in dct[x]:\n",
    "                    if y != fa:\n",
    "                        stack.append((y, x))\n",
    "            else:\n",
    "                x = ~x\n",
    "                res1 = res2 = 0\n",
    "                res1 += values[x]\n",
    "                a21 = 0\n",
    "                a22 = values[x]\n",
    "                flag = 0\n",
    "                for y in dct[x]:\n",
    "                    if y != fa:\n",
    "                        nex1, nex2 = dp1[y], dp2[y]\n",
    "                        res1 += nex1\n",
    "                        a21 += nex1 if nex1 > nex2 else nex2\n",
    "                        flag = 1\n",
    "                        a22 += nex2\n",
    "                if not flag:\n",
    "                    a22 = -inf\n",
    "                dp1[x] = res1\n",
    "                dp2[x] = a22 if a22 > a21 else a21\n",
    "\n",
    "        return dp2[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        g = [[] for i in range(n)]\n",
    "        for (u,v) in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "\n",
    "        topo = []\n",
    "        G, Q = [[] for i in range(n)], deque([0]) \n",
    "        while Q:\n",
    "            u= Q.popleft()\n",
    "            topo.append(u)\n",
    "            for v in g[u]:\n",
    "                if G[v]: continue\n",
    "                G[u].append(v)\n",
    "                Q.append(v)\n",
    "        topo.reverse()\n",
    "\n",
    "        sums = [0]*n\n",
    "        f = [0]*n\n",
    "        for u in topo:\n",
    "            if not G[u]: continue\n",
    "            for v in G[u]:\n",
    "                sums[u] += (sums[v] + values[v])\n",
    "                f[u] += f[v]\n",
    "            f[u] = max(f[u]+values[u], sums[u])\n",
    "\n",
    "        return f[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        adj = {}\n",
    "        for u, v in edges:\n",
    "            adj[v] = adj.get(v, []) + [u]\n",
    "            adj[u] = adj.get(u, []) + [v]\n",
    "        children = {}\n",
    "        unvisited = [True] * n\n",
    "        dq = deque([0])\n",
    "        seq = []\n",
    "        while dq:\n",
    "            u = dq.popleft()\n",
    "            if unvisited[u]:\n",
    "                seq.append(u)\n",
    "                unvisited[u] = False\n",
    "                for v in adj[u]:\n",
    "                    if unvisited[v]:\n",
    "                        children[u] = children.get(u, []) + [v]\n",
    "                        dq.append(v)\n",
    "        cs = [0] * n\n",
    "        for u in seq[::-1]:\n",
    "            for v in children.get(u, []):\n",
    "                cs[u] += cs[v] + values[v]\n",
    "        dp = [0] * n\n",
    "        for u in seq[::-1]:\n",
    "            if children.get(u, []):\n",
    "                total = values[u]\n",
    "                for v in children.get(u, []):\n",
    "                    total += dp[v]\n",
    "                dp[u] = max(cs[u], total)\n",
    "        return dp[0]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        g = [[] for _ in range(n)]\n",
    "        parent = [-1] * n\n",
    "        for e in edges:\n",
    "            g[e[0]].append(e[1])\n",
    "            g[e[1]].append(e[0])\n",
    "        q, head = [0], -1\n",
    "        visited = [False] * n\n",
    "        visited[0] = True\n",
    "        kids = [[] for _ in range(n)]\n",
    "        while head + 1 < len(q):\n",
    "            head += 1\n",
    "            u = q[head]\n",
    "            for v in g[u]:\n",
    "                if visited[v]:\n",
    "                    continue\n",
    "                q.append(v)\n",
    "                visited[v] = True\n",
    "                parent[v] = u\n",
    "                kids[u].append(v)\n",
    "        f = [[0, 0] for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            u = q[i]\n",
    "            p = parent[u]\n",
    "            if len(kids[u]) > 0:\n",
    "                f[u][1] += values[u]\n",
    "            if p != -1:\n",
    "                f[p][0] += values[u] + f[u][0]\n",
    "                f[p][1] += max(f[u])\n",
    "        return max(f[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedDict, SortedSet\n",
    "import random\n",
    "import copy\n",
    "import sys\n",
    "sys.setrecursionlimit(9999999)\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "\n",
    "        n = len(values)\n",
    "        lk = [[] for i in range(n)]\n",
    "        ch = [[] for i in range(n)]\n",
    "\n",
    "        for a, b in edges:\n",
    "            lk[a].append(b)\n",
    "            lk[b].append(a)\n",
    "\n",
    "        vis = [0] * n\n",
    "\n",
    "        que = deque()\n",
    "        que.append(0)\n",
    "        vis[0] = 1\n",
    "        tt = []\n",
    "        while len(que):\n",
    "            x = que.popleft()\n",
    "            tt.append(x)\n",
    "\n",
    "            for y in lk[x]:\n",
    "                if vis[y] == 0:\n",
    "                    vis[y] = 1\n",
    "                    que.append(y)\n",
    "                    ch[x].append(y)\n",
    "\n",
    "\n",
    "        dp = [[0, 0] for i in range(n)]\n",
    "\n",
    "        for x in tt[::-1]:\n",
    "            if len(ch[x]) == 0:\n",
    "                dp[x][1] = values[x]\n",
    "                dp[x][0] = 0\n",
    "\n",
    "                continue\n",
    "\n",
    "            dp[x][1] = values[x]\n",
    "            for y in ch[x]:\n",
    "                dp[x][1] += dp[y][1]\n",
    "\n",
    "\n",
    "            val1 = 0\n",
    "            for y in ch[x]:\n",
    "                val1 += dp[y][1]\n",
    "\n",
    "            val2 = values[x]\n",
    "            for y in ch[x]:\n",
    "                val2 += dp[y][0]\n",
    "\n",
    "            dp[x][0] = max(val1, val2)\n",
    "\n",
    "        return dp[0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        afterDict = defaultdict(list)\n",
    "        layerDict = defaultdict(int)\n",
    "        reverseLayerDict = defaultdict(list)\n",
    "        maxLayer = 0\n",
    "        \n",
    "        edgeDict = defaultdict(set)\n",
    "        for edge in edges:\n",
    "            edgeDict[edge[0]].add(edge[1])\n",
    "            edgeDict[edge[1]].add(edge[0])\n",
    "        \n",
    "        toBeCount = [0]\n",
    "        layerDict[0] = 1\n",
    "        while len(toBeCount) != 0:\n",
    "            tmp = toBeCount[0]\n",
    "            for i in edgeDict[tmp]:\n",
    "                if layerDict[i] == 0:\n",
    "                    toBeCount.append(i)\n",
    "                    afterDict[tmp].append(i)\n",
    "                    layerDict[i] = layerDict[tmp] + 1\n",
    "                    maxLayer = layerDict[i]\n",
    "            toBeCount.pop(0)\n",
    "            \n",
    "        for key in layerDict.keys():\n",
    "            reverseLayerDict[layerDict[key]].append(key)\n",
    "            \n",
    "        dp = [[0, 0] for i in range(len(values))]\n",
    "        \n",
    "        for layer in range(maxLayer, 0, -1):\n",
    "            nodes = reverseLayerDict[layer]\n",
    "            if layer == maxLayer:\n",
    "                for node in nodes:\n",
    "                    dp[node][0] = 0\n",
    "                    dp[node][1] = -1\n",
    "            else:\n",
    "                for node in nodes:\n",
    "                    # dp[node][0] 若这个节点不去掉，后面的节点随便你去不去掉\n",
    "                    afterNodes = afterDict[node]\n",
    "                    if len(afterNodes) == 0:\n",
    "                        dp[node][0] = 0\n",
    "                        dp[node][1] = -1\n",
    "                    else:\n",
    "                        dp[node][1] += values[node]\n",
    "                        for afterNode in afterNodes:\n",
    "                            dp[node][0] += max(values[afterNode] + dp[afterNode][0], dp[afterNode][1])\n",
    "                            dp[node][1] += max(dp[afterNode][0], dp[afterNode][1])\n",
    "            \n",
    "        \n",
    "        return max(dp[node][0], dp[node][1])\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        self.e = [[] for _ in range(n)]\n",
    "        self.s = [0] * n\n",
    "        self.s2 = [0] * n\n",
    "        self.values = values\n",
    "        for edge in edges:\n",
    "            self.e[edge[0]].append(edge[1])\n",
    "            self.e[edge[1]].append(edge[0])\n",
    "        self.dfs(0, -1)\n",
    "        return self.s2[0]\n",
    "    \n",
    "    def dfs(self, v, f):\n",
    "        # print(v, f)\n",
    "        son_s2 = 0\n",
    "        is_leaf = True\n",
    "        for u in self.e[v]:\n",
    "            if u != f:\n",
    "                is_leaf = False\n",
    "                self.dfs(u, v)\n",
    "                self.s[v] += self.s[u] + self.values[u]\n",
    "                son_s2 += self.s2[u]\n",
    "        if not is_leaf:\n",
    "            self.s2[v] = max(self.values[v] + son_s2, self.s[v])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "    \n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int: \n",
    "        s=sum(values)\n",
    "        n = len(values)\n",
    "        outs = [[] for _ in range(0,n)]\n",
    "        for v in edges:\n",
    "            outs[v[0]].append(v[1])\n",
    "            outs[v[1]].append(v[0])\n",
    "        m = dict()\n",
    "        return s-self.dfs(0,outs,values,m) \n",
    "    def dfs(self, root, outs, values, m):\n",
    "        m[root]=1\n",
    "        if len(outs[root])==0:\n",
    "            return values[root]\n",
    "        sum=0\n",
    "        for v in outs[root]:\n",
    "            if m.get(v) is None:\n",
    "                sum+=self.dfs(v,outs,values,m)\n",
    "        if sum==0:\n",
    "            return values[root]\n",
    "        return min(sum,values[root])        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        n=len(values);edge,f=[[] for i in range(n)],[[0,0] for i in range(n)]\n",
    "        for i in edges:edge[i[0]].append(i[1]);edge[i[1]].append(i[0])\n",
    "        def dfs(u,v):\n",
    "            for i in edge[u]:\n",
    "                if(i!=v):\n",
    "                    dfs(i,u)\n",
    "                    f[u][0]+=f[i][0]\n",
    "                    f[u][1]+=f[i][1]\n",
    "            if(f[u][0]!=0):f[u][1]=max(f[u][1]+values[u],f[u][0])\n",
    "            f[u][0]+=values[u]\n",
    "        dfs(0,0)\n",
    "        return f[0][1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        g=[[] for _ in values]\n",
    "        g[0].append(-1)\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        def dfs(x:int,fa:int)->int:\n",
    "            if len(g[x])==1:\n",
    "                return values[x]\n",
    "            loss=0\n",
    "            for y in g[x]:\n",
    "                if y!=fa:\n",
    "                    loss+=dfs(y,x)\n",
    "            return min(loss,values[x])\n",
    "        return sum(values)-dfs(0,-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, e: List[List[int]], v: List[int]) -> int:\n",
    "        n=len(e)+1\n",
    "        tree=[[] for i in range(n)]\n",
    "        for i,j in e:\n",
    "            tree[i].append(j)\n",
    "            tree[j].append(i)\n",
    "        def dfs(u,fa):\n",
    "            sf=st=0\n",
    "            for i in tree[u]:\n",
    "                if fa!=i:\n",
    "                    t,f=dfs(i,u)\n",
    "                    sf+=f\n",
    "                    st+=t\n",
    "            t=max(sf,st+v[u]) if sf>0 else 0\n",
    "            f=sf+v[u]\n",
    "            return t,f\n",
    "        t,f=dfs(0,-1)\n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        \n",
    "        def dfs(u, fa):\n",
    "            if len(g[u]) == 1 and fa != -1:\n",
    "                return values[u], 0\n",
    "            f1, f2 = 0, 0\n",
    "            \n",
    "            for j in g[u]:\n",
    "                if j != fa:\n",
    "                    g1, g2 = dfs(j, u)\n",
    "                    f1 += g1\n",
    "                    f2 += g2\n",
    "            return f1 + values[u], max(f1, f2 + values[u])\n",
    "        return dfs(0, -1)[1]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        menu = {}\n",
    "        for i in range(len(edges)):\n",
    "            if edges[i][0] in menu:\n",
    "                menu[edges[i][0]].append(edges[i][1])\n",
    "            else:\n",
    "                menu[edges[i][0]]=[edges[i][1]]\n",
    "            if edges[i][1] in menu:\n",
    "                menu[edges[i][1]].append(edges[i][0])\n",
    "            else:\n",
    "                menu[edges[i][1]]=[edges[i][0]]\n",
    "        menu[0].append(-1)\n",
    "        def dps(root,fa):\n",
    "            if len(menu[root])==1:\n",
    "                return values[root]\n",
    "            tmp=0\n",
    "            for node in menu[root]:\n",
    "                if node == fa:\n",
    "                    continue\n",
    "                tmp+=dps(node,root)\n",
    "            \n",
    "            return min(values[root],tmp)\n",
    "        return sum(values)-dps(0,-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        dic = {}\n",
    "        dicS = {}\n",
    "        dicC = {}\n",
    "        for i in range(len(edges)):\n",
    "            n1, n2 = edges[i][0], edges[i][1]\n",
    "            if(n1 in dic):\n",
    "                dic[n1].append(n2)\n",
    "            else:\n",
    "                dic[n1] = [n2]\n",
    "            if(n2 in dic):\n",
    "                dic[n2].append(n1)\n",
    "            else:\n",
    "                dic[n2] = [n1]\n",
    "\n",
    "        def cal(parent, father):\n",
    "            if(len(dic[parent]) == 1 and dic[parent][0] == father):\n",
    "                return 0\n",
    "            if(parent in dicC):\n",
    "                return dicC[parent]\n",
    "            s0 = 0\n",
    "            s1 = values[parent]\n",
    "            for item in dic[parent]:\n",
    "                if(item != father):\n",
    "                    s0 += sumP(item, parent)\n",
    "                    s1 += cal(item, parent)\n",
    "            dicC[parent] = max(s0,s1)\n",
    "            return max(s0, s1)\n",
    "\n",
    "\n",
    "        def sumP(parent, father):\n",
    "            if(len(dic[parent]) == 1 and dic[parent][0] == father):\n",
    "                return values[parent]\n",
    "            if(parent in dicS):\n",
    "                return dicS[parent]\n",
    "            ans = values[parent]\n",
    "            for item in dic[parent]:\n",
    "                if(item != father):\n",
    "                    ans += sumP(item, parent)\n",
    "            dicS[parent] = ans\n",
    "            return ans\n",
    "\n",
    "        return cal(0, -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        dp = [[] for _ in range(len(values))]\n",
    "        for i in edges:\n",
    "            dp[i[0]].append(i[1])\n",
    "            dp[i[1]].append(i[0])\n",
    "        dp[0].append(-1)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            dp1 = 0\n",
    "            dp2 = 0\n",
    "\n",
    "            if len(dp[i]) == 1:\n",
    "                return values[i], 0\n",
    "\n",
    "            for ii in dp[i]:\n",
    "                if j!=ii:\n",
    "                    a1,a2 = dfs(ii,i)\n",
    "                    dp1 += a1\n",
    "                    dp2 += a2\n",
    "\n",
    "            return dp1+values[i], max(dp2+values[i], dp1)\n",
    "        \n",
    "        return dfs(0,-1)[1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        gird = [[] for _ in range(n)]\n",
    "        for i, j in edges:\n",
    "            gird[i].append(j)\n",
    "            gird[j].append(i)\n",
    "        visited = [False]*n\n",
    "        b = [0] * n\n",
    "        def dfs0(i):\n",
    "            visited[i] = True\n",
    "            if b[i]: return b[i]\n",
    "            res = values[i]\n",
    "            \n",
    "            for j in gird[i]:\n",
    "                if j != i and not visited[j]:\n",
    "                    res += dfs0(j)\n",
    "            b[i] = res\n",
    "            return res\n",
    "        dfs0(0)\n",
    "        visited = [False]*n\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            visited[i] = True\n",
    "            if i != 0 and len(gird[i]) == 1:\n",
    "                return 0\n",
    "            # 不选\n",
    "            res1 = b[i] - values[i]\n",
    "            \n",
    "            #选\n",
    "            res2 = values[i]\n",
    "            for j in gird[i]:\n",
    "                if j != i and not visited[j]:\n",
    "                    res2 += dfs(j)\n",
    "            return max(res1, res2)\n",
    "        return dfs(0)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        # 每个元素可以加入到分数  也可以不加入\n",
    "        # 当前元素如果不加入，那么所有的孩子都全都可以加入\n",
    "        # 如果当前元素加入，那么所有的孩子都必须要收礼物\n",
    "\n",
    "        graph = defaultdict(list)\n",
    "        for a,b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        \n",
    "        # s==0 还没选择过\n",
    "        # s==1 不需要保留了\n",
    "        @cache\n",
    "        def dfs(node, fa,s):\n",
    "            if len(graph[node]) == 1 and node != 0:\n",
    "                #叶子\n",
    "                if s == 0: return 0\n",
    "                return values[node]\n",
    "            \n",
    "            sel = 0\n",
    "            unsel = values[node]\n",
    "            for next in graph[node]:\n",
    "                if next != fa:\n",
    "                    sel += dfs(next,node,1)\n",
    "                    unsel += dfs(next,node,0)\n",
    "            if s == 0: return max(sel, unsel)\n",
    "            return sel + values[node]\n",
    "            \n",
    "        return dfs(0,-1,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        d = collections.defaultdict(set)\n",
    "        for u, v in edges:\n",
    "            d[u].add(v)\n",
    "            d[v].add(u)\n",
    "        def dfs(last, u):\n",
    "            ans1 = 0\n",
    "            ans2 = 0\n",
    "            for v in d[u]:\n",
    "                if v != last:\n",
    "                    value1, value2 = dfs(u, v)\n",
    "                    ans1 += value1\n",
    "                    ans2 += value2\n",
    "            out1 = ans1 + values[u]\n",
    "            if ans1 == 0:\n",
    "                out2 = 0\n",
    "            else:\n",
    "                out2 = max(ans2 + values[u], ans1)\n",
    "            return out1, out2\n",
    "        return dfs(-1, 0)[1]\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        g = [[] for _ in values]\n",
    "        g[0].append(-1)  # 避免误把根节点当作叶子\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        @cache\n",
    "        def dfs(cnode:int, isfather, father):\n",
    "            if isfather:\n",
    "                return values[cnode] + sum(dfs(son, True, cnode) for son in g[cnode] if son != father)\n",
    "            else:\n",
    "                sons = g[cnode]\n",
    "                if len(sons) == 1:\n",
    "                    if values[cnode]:\n",
    "                        return 0\n",
    "                    else:\n",
    "                        return -1\n",
    "                if values[cnode]:\n",
    "                    res_val = values[cnode]\n",
    "                    for son in sons:\n",
    "                        if son == father:\n",
    "                            continue\n",
    "                        a = dfs(son, False, cnode)\n",
    "                        if a == -1:\n",
    "                            res_val = -1\n",
    "                            break\n",
    "                        res_val += a\n",
    "                    return max(sum(dfs(son, True, cnode) for son in g[cnode] if son != father), res_val)\n",
    "                else:\n",
    "                    res_val = 0\n",
    "                    for son in sons:\n",
    "                        a = dfs(son, False, cnode)\n",
    "                        if a == -1:\n",
    "                            res_val = -1\n",
    "                            break\n",
    "                        res_val += a\n",
    "                    return res_val\n",
    "        # return dfs(0, False)\n",
    "\n",
    "            \n",
    "        return dfs(0, False, -1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        d = collections.defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            d[a].append(b)\n",
    "            d[b].append(a)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(cur, far, save):\n",
    "            if cur != 0 and len(d[cur]) == 1 and not save:\n",
    "                return 0\n",
    "            res1, res2 = 0, values[cur] #不选， 选\n",
    "            for nxt in d[cur]:\n",
    "                if nxt != far:\n",
    "                    res1 += dfs(nxt, cur, True)\n",
    "                    res2 += dfs(nxt, cur, save)\n",
    "            return max(res1, res2)\n",
    "        \n",
    "        return dfs(0, -1, False)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "            \n",
    "        @lru_cache(None)\n",
    "        def dfs(u, p, have_point):\n",
    "            if have_point:\n",
    "                ans = values[u]\n",
    "                for v in graph[u]:\n",
    "                    if v == p:\n",
    "                        continue\n",
    "                    ans += dfs(v, u, True)\n",
    "                return ans\n",
    "            else:\n",
    "                if len(graph[u]) == 1 and p != -1:\n",
    "                    return 0\n",
    "                ans1, ans2 = 0, values[u]\n",
    "                for v in graph[u]:\n",
    "                    if v == p:\n",
    "                        continue\n",
    "                    ans1 += dfs(v, u, True)\n",
    "                    ans2 += dfs(v, u, False)\n",
    "                return max(ans1, ans2)\n",
    "        \n",
    "        return dfs(0, -1, False)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        dp = [[0] * 2 for _ in range(n)]\n",
    "\n",
    "        graph = defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "\n",
    "        # s->0 上面还没选过，  s->1 上面已经选过了\n",
    "        @cache\n",
    "        def dfs(node, fa, s):\n",
    "            if s == 1:\n",
    "                ans = values[node]\n",
    "                for next in graph[node]:\n",
    "                    if next != fa:\n",
    "                        ans += dfs(next, node, 1)\n",
    "                return ans\n",
    "            if len(graph[node]) == 1 and node != 0:\n",
    "                return 0\n",
    "            #可以选择保留这个节点\n",
    "            ans = 0\n",
    "            for next in graph[node]:\n",
    "                if next != fa:\n",
    "                    ans += dfs(next, node,1)\n",
    "\n",
    "            #也可以选择不保留\n",
    "            notsel = values[node]\n",
    "            for next in graph[node]:\n",
    "                if next != fa:\n",
    "                    notsel += dfs(next, node, 0)\n",
    "            return max(ans, notsel)\n",
    "        return dfs(0,-1,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        n = len(edges) + 1\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(u, fa, st, valid):\n",
    "            if len(g[u]) == 1 and g[u][0] == fa and not valid: return 0\n",
    "            cur = values[u] if st else 0\n",
    "            res1 = res2 = res3 = 0\n",
    "            if valid:\n",
    "                for nxt in g[u]:\n",
    "                    if nxt == fa: continue\n",
    "                    res1 += dfs(nxt, u, 1, 1)\n",
    "            else:\n",
    "                if st == 1:\n",
    "                    for nxt in g[u]:\n",
    "                        if nxt == fa: continue\n",
    "                        res2 += max(dfs(nxt, u, 1, 0), dfs(nxt, u, 0, 1))\n",
    "                else:\n",
    "                    for nxt in g[u]:\n",
    "                        if nxt == fa: continue\n",
    "                        res3 += dfs(nxt, u, 1, 1)\n",
    "            return max(res1, res2, res3) + cur\n",
    "        return max(dfs(0, -1, 0, 1), dfs(0, -1, 1, 0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def maximumScoreAfterOperations(self, edges, values):\n",
    "\n",
    "        n = len(values)\n",
    "        childrens = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            childrens[a] += [b]\n",
    "            childrens[b] += [a]\n",
    "\n",
    "        visited = [False for _ in range(n)]\n",
    "        \n",
    "        @cache\n",
    "        def dfs(node, reserve):\n",
    "            children = []\n",
    "            for child in childrens[node]:\n",
    "                if not visited[child]:\n",
    "                    children += [child]\n",
    "\n",
    "            value = values[node]\n",
    "            if not children:\n",
    "                return 0 if not reserve else value\n",
    "\n",
    "            scores = []\n",
    "            if not reserve:\n",
    "                score = 0\n",
    "                for child in children:\n",
    "                    visited[child] = True\n",
    "                    score += dfs(child, True)\n",
    "                    visited[child] = False\n",
    "                scores += [score]\n",
    "\n",
    "            score = 0\n",
    "            for child in children:\n",
    "                visited[child] = True\n",
    "                score += dfs(child, reserve)\n",
    "                visited[child] = False\n",
    "            scores += [score + value]\n",
    "\n",
    "            return max(scores)\n",
    "\n",
    "        visited[0] = True\n",
    "        return dfs(0, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        n=len(values)\n",
    "        children=[set() for _ in range(n)]\n",
    "        visited=set([0])\n",
    "        def add(i):\n",
    "            visited.add(i)\n",
    "            for j in children[i]:\n",
    "                children[j].remove(i)\n",
    "                add(j)\n",
    "                \n",
    "        for i,j in edges:\n",
    "            if i in visited:\n",
    "                children[i].add(j)\n",
    "                add(j)\n",
    "            elif j in visited:\n",
    "                children[j].add(i)\n",
    "                add(i)\n",
    "            else:\n",
    "                children[i].add(j)\n",
    "                children[j].add(i)\n",
    "                \n",
    "        @cache\n",
    "        def f(i,keep):\n",
    "            ans=0\n",
    "            for c in children[i]:\n",
    "                ans+=f(c,False)\n",
    "            if not keep:\n",
    "                return ans+values[i]\n",
    "            ans1=0\n",
    "            if not children[i]:\n",
    "                return 0\n",
    "            for c in children[i]:\n",
    "                ans1+=f(c,True)\n",
    "            # print(i,'qu:',ans1+values[i],'buqu:',ans)\n",
    "            return max(ans,ans1+values[i])\n",
    "    \n",
    "        return f(0,True)\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        # dp(i, flag): 表示以i为根节点的树能达到的最大和，flag表示是否上面已有非0\n",
    "        \n",
    "        node2child = collections.defaultdict(set)\n",
    "        for edge in edges:\n",
    "            node2child[edge[0]].add(edge[1])\n",
    "            node2child[edge[1]].add(edge[0])\n",
    "        stack = [0]\n",
    "        while stack:\n",
    "            idx = stack[0]\n",
    "            stack = stack[1:]\n",
    "            for child in node2child[idx]:\n",
    "                node2child[child].remove(idx)\n",
    "                stack.append(child)\n",
    "                \n",
    "        \n",
    "        \n",
    "        \n",
    "        @cache\n",
    "        def dp(i, flag):\n",
    "            if not node2child[i]:\n",
    "                if flag:\n",
    "                    if values[i] == 0:\n",
    "                        return -float(\"inf\")\n",
    "                    else:\n",
    "                        return 0\n",
    "                else:\n",
    "                    ans = values[i]\n",
    "                    return ans\n",
    "            else:\n",
    "                if not flag:\n",
    "                    ans = values[i]\n",
    "                    for child in list(node2child[i]):\n",
    "                        ans += dp(child, False)\n",
    "                    return ans\n",
    "                else:\n",
    "                    if values[i] == 0:\n",
    "                        ans = 0\n",
    "                        for child in list(node2child[i]):\n",
    "                            ans = ans + dp(child, True)\n",
    "                        return ans\n",
    "                    else:\n",
    "                        ans1 = 0\n",
    "                        # case 1:\n",
    "                        for child in list(node2child[i]):\n",
    "                            ans1 = ans1 + dp(child, False)\n",
    "                        # case 2:\n",
    "                        ans2 = values[i]\n",
    "                        for child in list(node2child[i]):\n",
    "                            ans2 = ans2 + dp(child, True)\n",
    "                        if ans2 > ans1:\n",
    "                            return ans2\n",
    "                        else:\n",
    "                            return ans1\n",
    "        return dp(0, True)\n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], val: List[int]) -> int:\n",
    "        n=len(edges)+1\n",
    "        g=[[] for _ in range(n)]\n",
    "        for a,b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        \n",
    "        vis=[False]*n\n",
    "        t=[[] for _ in range(n)]\n",
    "        def tree(node):\n",
    "            vis[node]=True\n",
    "            son=[x for x in g[node] if not vis[x]]\n",
    "            t[node].extend(son)\n",
    "            for next in son:\n",
    "                tree(next)\n",
    "        tree(0)\n",
    "        # print(t)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(node:int,select:bool)->tuple[int]:\n",
    "            if not t[node]:\n",
    "                if select:\n",
    "                    return (0,val[node])\n",
    "                else:\n",
    "                    return (0,0)\n",
    "            if select:\n",
    "                ans=0\n",
    "                for son in t[node]:\n",
    "                    ans+=dfs(son,True)[1]\n",
    "                return (ans,ans+val[node])\n",
    "            else:\n",
    "                a=0\n",
    "                b=val[node]\n",
    "                for son in t[node]:\n",
    "                    x,y=dfs(son,select)\n",
    "                    i,j=dfs(son,True)\n",
    "                    a+=max(i,j)\n",
    "                    b+=max(x,y)\n",
    "                return (a,b)\n",
    "        return max(dfs(0,False))\n",
    "    \n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        children = [[] for _ in range(n)]\n",
    "        for f,t in edges:\n",
    "            children[f].append(t)\n",
    "            children[t].append(f)\n",
    "        \n",
    "        def dfs(i, fa):\n",
    "            ss = sum(dfs(c, i) for c in children[i] if c!=fa)\n",
    "            if ss>0: return min(values[i],ss)\n",
    "            return values[i]\n",
    "        return sum(values) - dfs(0,-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        path = defaultdict(list)\n",
    "        for x, y in edges:\n",
    "            path[x].append(y)\n",
    "            path[y].append(x)\n",
    "        def dfs(cur, prev):\n",
    "            if cur != 0 and len(path[cur]) == 1:\n",
    "                return values[cur]\n",
    "            return min(values[cur], sum(dfs(next, cur) for next in path[cur] if next != prev))\n",
    "        return sum(values) - dfs(0, -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        g = [[] for _ in values]\n",
    "        g[0].append(-1)\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "\n",
    "        total = [0] * len(values)\n",
    "        def cal_sum(u, fa):\n",
    "            total[u] = values[u]\n",
    "            for v in g[u]:\n",
    "                if v != fa:\n",
    "                    cal_sum(v, u)\n",
    "                    total[u] += total[v]\n",
    "\n",
    "        cal_sum(0, -1)\n",
    "\n",
    "        def dfs(u, fa):\n",
    "            if len(g[u]) == 1:\n",
    "                return 0 \n",
    "            not_do = sum(total[v] for v in g[u] if v != fa)\n",
    "            do_it = values[u] + sum(dfs(v, u) for v in g[u] if v != fa)\n",
    "            return max(not_do, do_it)\n",
    "\n",
    "        return dfs(0, -1)\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # g = [[] for _ in values]\n",
    "        # g[0].append(-1)  # 避免误把根节点当作叶子\n",
    "        # for x, y in edges:\n",
    "        #     g[x].append(y)\n",
    "        #     g[y].append(x)\n",
    "\n",
    "        # # dfs(x, fa) 计算以 x 为根的子树是健康时，失去的最小分数\n",
    "        # def dfs(x: int, fa: int) -> int:\n",
    "        #     if len(g[x]) == 1:  # x 是叶子\n",
    "        #         return values[x]\n",
    "        #     loss = 0  # 第二种情况\n",
    "        #     for y in g[x]:\n",
    "        #         if y != fa:\n",
    "        #             loss += dfs(y, x)  # 计算以 y 为根的子树是健康时，失去的最小分数\n",
    "        #     return min(values[x], loss)  # 两种情况取最小值\n",
    "        # return sum(values) - dfs(0, -1)\n",
    "\n",
    "\n",
    "        # n = len(values)\n",
    "        # graph = [[] for _ in range(n)]\n",
    "        # outDegree = [0]*n\n",
    "\n",
    "        # for u, v in edges:\n",
    "        #     graph[u].append(v)\n",
    "        #     outDegree[u] += 1\n",
    "\n",
    "        # def isHealthy(root):\n",
    "        #     if values[root] == 0 and not graph[root]:\n",
    "        #         return False\n",
    "        #     for nxt in graph[root]:\n",
    "        #         values[nxt] = values[root] + values[nxt]\n",
    "        #         if values[nxt] == 0 and not isHealthy(nxt):\n",
    "        #             return False        \n",
    "        #     return True\n",
    "\n",
    "        # dp = [0] * n \n",
    "        # base case\n",
    "        # for i in range(n):\n",
    "        #     if not graph[i]:  # 叶子结点\n",
    "        #         dp[i] = values[i]\n",
    "        \n",
    "        # dp[i] = max(values[i] + dp[graph[i]], values[graph[i]])  # max(选自己， 不选自己)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        # 构造一颗树\n",
    "        g = [[] for _ in values]\n",
    "        g[0].append(-1)\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "\n",
    "        # total[i]表示以节点i为根节点的子树的元素和\n",
    "        total = [0] * len(values)\n",
    "\n",
    "        def cal_sum(u, fa):\n",
    "            # 第一次dfs，计算整棵树的元素和\n",
    "            total[u] = values[u]\n",
    "            for v in g[u]:\n",
    "                if v != fa:\n",
    "                    cal_sum(v, u)\n",
    "                    total[u] += total[v]\n",
    "        cal_sum(0, -1)\n",
    "\n",
    "        def dfs(u, fa):\n",
    "            if len(g[u]) == 1:\n",
    "                return 0\n",
    "            # 不选当前节点，可以选所有u的子树之和（不含u）\n",
    "            f0 = sum(total[v] for v in g[u] if v!= fa)\n",
    "\n",
    "            # 选当前节点，转化为求以v为根的子树是健康的能获得的最大分数\n",
    "            f1 = values[u] + sum(dfs(v, u) for v in g[u] if v != fa)\n",
    "\n",
    "            return max(f0, f1)\n",
    "        return dfs(0, -1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumScoreAfterOperations(self, edges: List[List[int]], values: List[int]) -> int:\n",
    "        g = [[] for _ in values]\n",
    "        g[0].append(-1)\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        \n",
    "        @cache\n",
    "        def cal_sum(u, fa):\n",
    "            tot = values[u]\n",
    "            for v in g[u]:\n",
    "                if v != fa:\n",
    "                    tot += cal_sum(v, u)\n",
    "            return tot\n",
    "        \n",
    "        # 以u为根的子树是健康的能获得的最大分数\n",
    "        def dfs(u, fa):\n",
    "            if len(g[u]) == 1:\n",
    "                return 0\n",
    "            #不选当前节点，可以选所有u的子树之和（不含u）\n",
    "            f0 = sum(cal_sum(v, u) for v in g[u] if v != fa)\n",
    "            \n",
    "            #选当前节点，转化为求以v为根的子树是健康的能获得的最大分数\n",
    "            f1 = values[u] + sum(dfs(v, u) for v in g[u] if v != fa)\n",
    "            return max(f0, f1)\n",
    "        \n",
    "        return dfs(0, -1)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
